#include<stdio.h>

void insertion_sort(int unsorted_array[], int num_elements){
    if (num_elements<2) {
        return;
    }
    for (int i=1; i<num_elements; i++) {
        int insertValue = unsorted_array[i];//这里是暂存需要插入元素
        int j = i-1;
        //从右向左比较元素
        for (; j>=0 && insertValue<unsorted_array[j]; j--) {
            unsorted_array[j+1] = unsorted_array[j];
        }
        unsorted_array[j+1] = insertValue;
    }
}

void quick_sort(int unsorted_array[], int num_elements){
    for (int i = 0; i < num_elements; i++) {
        int start = 0,end = num_elements-1;
        while (start<end){
            int base = unsorted_array[i];
            while (unsorted_array[start]<base){
                start++;
            }
            while (unsorted_array[end]>base){
                end--;
            }
            int temp=unsorted_array[start];
            unsorted_array[start]=unsorted_array[end];
            unsorted_array[end]=temp;
        }
    }
}

void HeapAdjust(int a[],int s,int m)//一次筛选的过程
{
    int rc,j;
    rc=a[s];
    for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选
    {
        if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标
        if(rc>a[j]) break;
        a[s]=a[j];s=j;
    }
    a[s]=rc;//插入
}

void heap_sort(int unsorted_array[], int num_elements){
    int temp,i,j;
    for(i=num_elements/2;i>0;i--)//通过循环初始化顶堆
    {
        HeapAdjust(unsorted_array,i,num_elements);
    }
    for(i=num_elements;i>0;i--)
    {
        temp=unsorted_array[1];
        unsorted_array[1]=unsorted_array[i];
        unsorted_array[i]=temp;//将堆顶记录与未排序的最后一个记录交换
        HeapAdjust(unsorted_array,1,i-1);//重新调整为顶堆
    }
}


void main() {
    int a[] = {1,9,8,7,6,5,0,2,3,4};
    insertion_sort(a, 10);
    for(int i=0; i<10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n"); //  此时应该看到输出为 0 1 2 3 4 5 6 7 8 9


    quick_sort(a, 10);
    for(int i=0; i<10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n"); //  此时应该看到输出为 0 1 2 3 4 5 6 7 8 9


    heap_sort(a, 10);
    for(int i=0; i<10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n"); //  此时应该看到输出为 0 1 2 3 4 5 6 7 8 9
}
